1. Field of the Invention
The present invention relates to content-addressable memories (CAM) and, in particular, to methods and apparatus for detecting multiple matches in the associative array of a content addressable memory used for a translation look-aside buffer.
2. Discussion of the Prior Art
Content addressable memories are used in a variety of applications ranging from sorting large databases to image recognition. In a content addressable memory, a multi-bit boolean data word is broadcasted to an associative array. The associative array compares the incoming data word to each of the data words stored in the rows of the array. When a match occurs, that is, when the bits of the input word match the bits of a word stored in any row of the associative array, a match signal is generated that is used to address a secondary array.
Under certain conditions, multiple matches can occur in the associative array. For example, if the system software is poorly written, it can cause redundant words to appear in the array. Hardware can, through random start-up states or several other well-known mechanisms, fail to write or retain unique data in the array. Furthermore, alpha particles, a random event, may cause memory cells in the associative array to change state.
In some applications, multiple matches in the associative array are acceptable and additional circuitry is provided to resolve that condition. However, other applications, such as microprocessors, are not so forgiving.
A content addressable memory is typically used in a microprocessor to create a look-up table, commonly referred to as a translation look-aside buffer (TLB), that relates local or cache memory data to some hierarchical location in the microprocessor's main memory. In the most simple form, if data has been transferred from main memory to a local cache memory, then the central processing unit needs to know that the data is stored locally. To make this determination, part of the address of the data from main memory is compared in the content addressable memory. If there is a match or "hit", that data plus the address that is generated from the CAM's secondary array, is used to inform the CPU where to find the data. This look-up mechanism must be unique. That is, a translation from cache memory and main memory can have no ambiguity. Therefore, either a no-hit or single hit situation are the only two possible states that will be tolerated.
FIG. 1 shows an example of a four word associative array with a five bit word width. In the FIG. 1 example, when an incoming five bit data word B.sub.0 -B.sub.4 is broadcasted to the associative array, the bits at each site in the array are checked en-masse. That is, the following logic is solved for each storage site in the array: EQU An xor Bn=Mn
Where An is the stored bit value in column n of a row in the associative array and Bn is the broadcasted bit at column n.
A word match signal MATCH can then be generated as follows: EQU M0 and M1 and M2 and M3 and M4=MATCH
That is, if all the individual bits in a row of the associative array match the broadcasted word, then the MATCH signal active state is generated for that row. In the FIG. 1 example, if the broadcasted word B.sub.0 -B.sub.4 consists of the bit sequence 00101, then word two (WORD2) in the associative array is uniquely matched.
The match signal out of the associative array addresses a secondary array, as shown in FIG. 2. More specifically, when a match occurs in the associative array, the active match signal generated for the matched row turns on an associated row driver to the secondary array. For example, if WORD2 is a match in the associative array, then its associated driver D2 is turned on. Note that a "no match" state could be easily determined by forming the logical "OR" of all of the match signal outputs of the associative array. A no match condition is equal to a false or "0" output. Further note that two or more matches in the associative array cause two or more row drivers to be turned on, a situation that leaves the outputs C.sub.0 -C.sub.3 of the secondary array in an ambiguous state.
One of the consequences of a multiple match malfunction in the TLB of a microprocessor is that it can take several processor clock cycles to detect. These malfunctions are hard to trouble shoot, since the states of the processor move further away from the error state with each clock cycle prior to detection. Initialization of the software to detect multiple matches on the fly adds overhead to system operation, thus slowing the system down.
In addition to system malfunction from a software standpoint, the driver circuit and power supply distribution mechanism of the translation look-aside buffer may be over-stressed due to the multiple matches. Since driver speed is very critical to fast system operation, a greater relative power is used on the driver circuit. If two or more drivers are on at any given time, these circuits and their supply traces are over-stressed with large current densities. This may cause other circuits to operate in an undesired mode, or, in the worst case, can lead to catastrophic failure of the circuit.
Existing solutions to the problem of multiple match detection in an associative array rely on either sequential detection mechanisms, inhibiting operations, or binary search techniques. Each of these solutions requires extra circuitry in the critical circuit path, requires a relatively long time to resolve the problem, and uses a relatively large amount of chip area to implement.